package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by tiang on 2018/11/23.
 * 复制无向图
 */
public class CloneGraph {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        HashMap<UndirectedGraphNode, UndirectedGraphNode> old2new = new HashMap<>();
        return cloneGraphSub(node, old2new);
    }

    private UndirectedGraphNode cloneGraphSub(UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> old2new){
        if(node == null)
            return null;
        if(old2new.containsKey(node))
            return old2new.get(node);
        UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
        old2new.put(node, newNode);
        for(UndirectedGraphNode n : node.neighbors){
            newNode.neighbors.add(cloneGraphSub(n, old2new));
        }
        return newNode;
    }
}
class UndirectedGraphNode {
    int label;
    List<UndirectedGraphNode> neighbors;

    UndirectedGraphNode(int x) {
        label = x;
        neighbors = new ArrayList<UndirectedGraphNode>();
    }
}